package test0316;

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/3/30 14:17
 * 实现顺序表
 */
public class MyArrayList {

    private int[] data; // 用于存储数据
    private final int DEFAULT_SIZE = 10; // 初始容量默认为10
    private int size; // 标记顺序表实际元素个数

    public MyArrayList() {
        this.data = new int[DEFAULT_SIZE];
        this.size = 0;
    }

    // 遍历顺序表, 并打印
    public void display() {
        if (size == 0) {
            System.out.println("当前顺序表为空!");
            return;
        }
        System.out.print("当前顺序表: ");
        for (int i = 0; i < size; i++) {
            System.out.print(this.data[i] + " ");
        }
        System.out.println();
    }

    // 判断当前顺序表是否包含指定的 key
    public boolean contains(int key) {
        for (int i = 0; i < size; i++) {
            if (data[i] == key) {
                return true;
            }
        }
        return false;
    }

    // 返回对应 key 第一次出现的索引, 如果不存在 返回-1
    public int indexOf(int key) {
        for (int i = 0; i < size; i++) {
            if (data[i] == key) {
                return i;
            }
        }
        return -1;
    }

    // 添加 data 到顺序表的末尾
    public void add(int data) {
        if (isFull()) {
            // 如果已经满了, 则需要进行扩容
            resize();
        }
        this.data[size] = data;
        size++;
    }

    // 添加 data 到指定的 index
    public void add(int index, int data) {
        if (index < 0 || index > size) {
            // 检验插入的位置是否合法
            throw new RuntimeException("当前插入的 index 位置不合法!");
        }
        if(isFull()) {
            // 如果已经满了, 需要先进行扩容
            resize();
        }
        // 先将[index, size-1]位置的所有元素向后移动, 再把 data 插入到 index 位置
        for (int i = size-1; i >= index; i--) {
            this.data[i+1] = this.data[i];
        }
        this.data[index] = data;
        size++;
    }

    // 删除 index 位置的元素
    public void remove(int index) {
        checkIndex(index);
        // 从 index+1 位置向前覆盖
        for (int i = index; i < size-1; i++) {
            this.data[i] = this.data[i+1];
        }
        size--;
        this.data[size] = 0;
    }

    // 获取 index 位置的值
    public int get(int index) {
        checkIndex(index);
        return this.data[index];
    }

    // 更新 index 位置的值
    public void set(int index, int data) {
        checkIndex(index);
        this.data[index] = data;
    }

    // 判断是否已满
    public boolean isFull() {
        return this.data.length == size;
    }

    // 判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }


    // 获取当前顺序表的使用大小
    public int size() {
        return size;
    }

    // 清空顺序表
    public void clear() {
        this.data = new int[DEFAULT_SIZE];
        size = 0;
    }

    // 用于查找, 删除, 更新值时判断位置是否合法
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("当前查看的 index 位置不合法!");
        }
    }

    // 用于顺序表的扩容
    private void resize() {
        this.data = Arrays.copyOf(data, 2 * size);
    }
}
